﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<string>
#include<bitset>
using namespace std;

//倒置字符串（字符串）
//https://www.nowcoder.com/practice/f0db4c36573d459cae44ac90b90c6212?tpId=182&tqId=34789&ru=/exam/oj

//暴力
//int main()
//{
//	string s1, s2, ret;
//	getline(cin, s1);
//	cin >> s2;
//	
//	for (auto e1 : s1)
//	{
//		int flag = 1;
//		for (auto e2 : s2)
//		{
//			if (e1 == e2)
//				flag = 0;
//		}
//		if (flag)
//			ret += e1;
//	}
//	cout << ret;
//}

//哈希
//int main()
//{
//	string s1, s2;
//	getline(cin, s1);
//	cin >> s2;
//
//	bitset<300> hash;
//	for (auto ch : s2)
//	{
//		hash[ch] = 1;
//	}
//
//	string ret;
//	for (auto ch : s1)
//	{
//		if (!hash[ch])
//			ret += ch;
//	}
//
//	cout << ret << endl;
//
//	return 0;
//}


//两个链表的第⼀个公共结点（链表）
//https://www.nowcoder.com/practice/6ab1d9a29e88450685099d45c9e31e46?tpId=13&tqId=11189&ru=/exam/oj

struct ListNode {
	int val;
	struct ListNode *next;
	ListNode(int x) :
			val(x), next(NULL) {
	}
};

//class Solution {
//public:
//	ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
//		int len1 = 0, len2 = 0;
//		ListNode* cur = pHead1;
//		while (cur)
//		{
//			len1++;
//			cur = cur->next;
//		}
//
//		cur = pHead2;
//		while (cur)
//		{
//			len2++;
//			cur = cur->next;
//		}
//
//		ListNode* it1 = pHead1, * it2 = pHead2;
//		while (len1 != len2)
//		{
//			if (len1 > len2)
//			{
//				it1 = it1->next;
//				len1--;
//			}
//			else if (len2 > len1)
//			{
//				it2 = it2->next;
//				len2--;
//			}
//		}
//		while (it1 != it2)
//		{
//			it1 = it1->next;
//			it2 = it2->next;
//		}
//		return it1;
//	}
//};


// 简化
// 同时遍历，每个链表走完后从另一个链表头开始，则两个链表⾛的路程相同，找到相交点。

//class Solution {
//public:
//	ListNode* FindFirstCommonNode(ListNode* pHead1, ListNode* pHead2) {
//		ListNode* cur1 = pHead1, * cur2 = pHead2;
//		while (cur1 != cur2)
//		{
//			cur1 = (cur1 == nullptr ? pHead2 : cur1->next);
//			cur2 = (cur2 == nullptr ? pHead1 : cur2->next);
//		}
//		return cur1;
//	}
//};


//mari和shiny（动态规划 - 线性dp）
//https://ac.nowcoder.com/acm/problem/26226


//int main()
//{
//	int n;
//	string s;
//	cin >> n >> s;
//
//	long long countS = 0, countSH = 0, ret = 0;
//	for (int i = 0; i < n; i++)
//	{
//		if (s[i] == 's')
//			countS++;
//		else if (s[i] == 'h')
//			countSH += countS;
//		else if (s[i] == 'y')
//			ret += countSH;
//	}
//	cout << ret << endl;
//
//	return 0;
//}
